#include<iostream>

using namespace std;

int qmi(int a,int b,int p)
{
    int res=1;
    while(b)
    {
        if(b&1)res=(long long)res*a%p;
        b>>=1;
        a=(long long)a*a%p;
    }
    return res;
}

int main()
{
    int n;scanf("%d",&n);
    
    while(n--)
    {
        int a,b,p;scanf("%d%d%d",&a,&b,&p);
        cout<<qmi(a,b,p)<<endl;
    }
    return 0;
}